{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #BST Sequences LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #backtracking #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #回溯 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: BSTSequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。</p>\n",
    "\n",
    "<p>给定一个由<strong>不同节点</strong>组成的二叉搜索树 <code>root</code>，输出所有可能生成此树的数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [2,1,3]\n",
    "<strong>输出: </strong>[[2,1,3],[2,3,1]]\n",
    "解释: 数组 [2,1,3]、[2,3,1] 均可以通过从左向右遍历元素插入树中形成以下二叉搜索树\n",
    "&nbsp;      2 \n",
    "&nbsp;     / \\ \n",
    "&nbsp;    1   3\n",
    "</pre>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><strong>示例</strong><strong>&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [4,1,null,null,3,2]\n",
    "<strong>输出: </strong>[[4,1,3,2]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉搜索树中的节点数在<meta charset=\"UTF-8\" />&nbsp;<code>[0, 1000]</code>&nbsp;的范围内</li>\n",
    "\t<li><code>1 &lt;= 节点值&nbsp;&lt;= 10^6</code></li>\n",
    "\t<li>\n",
    "\t<p>用例保证符合要求的数组数量不超过 <code>5000</code></p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bst-sequences-lcci](https://leetcode.cn/problems/bst-sequences-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bst-sequences-lcci](https://leetcode.cn/problems/bst-sequences-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        res = []\n",
    "        def bst(cand, seq, res):\n",
    "            if len(cand) == 0:\n",
    "                res.append(list(seq))\n",
    "                return\n",
    "            for node in list(cand):\n",
    "                cand.remove(node)\n",
    "                if node.left:\n",
    "                    cand.add(node.left)\n",
    "                if node.right:\n",
    "                    cand.add(node.right)\n",
    "                seq.append(node.val)\n",
    "                bst(cand, seq, res)\n",
    "                seq.pop()\n",
    "                if node.left:\n",
    "                    cand.remove(node.left)\n",
    "                if node.right:\n",
    "                    cand.remove(node.right)\n",
    "                cand.add(node)\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        bst({root}, [], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        self.res = []\n",
    "        self.temp = [root.val]\n",
    "        \n",
    "        self.find_path(root, [])\n",
    "        return self.res\n",
    "\n",
    "    def find_path(self, node, q):\n",
    "        if node.left:\n",
    "            q.append(node.left)\n",
    "        if node.right:\n",
    "            q.append(node.right)\n",
    "        if not q:\n",
    "            self.res.append(self.temp[:])\n",
    "            return\n",
    "        for i, n in enumerate(q):\n",
    "            self.temp.append(n.val)\n",
    "            nq = q[:i] + q[i + 1:]\n",
    "            self.find_path(n, nq)\n",
    "            self.temp.pop()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        ans = [[root.val]]\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            \n",
    "            if node.left:\n",
    "                res = []\n",
    "                while ans:\n",
    "                    arr = ans.pop(0)\n",
    "                    for i in range(len(arr)-1, -1, -1):\n",
    "                        arr_copy = deepcopy(arr)\n",
    "                        arr_copy.insert(i+1, node.left.val)\n",
    "                        res.append(arr_copy)\n",
    "                        if arr[i]==node.val:\n",
    "                            break\n",
    "                ans = res\n",
    "                print(ans)\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                res = []\n",
    "                while ans:\n",
    "                    arr = ans.pop(0)\n",
    "                    for i in range(len(arr)-1, -1, -1):\n",
    "                        arr_copy = deepcopy(arr)\n",
    "                        arr_copy.insert(i+1, node.right.val)\n",
    "                        res.append(arr_copy)\n",
    "                        if arr[i]==node.val:\n",
    "                            break\n",
    "                ans = res\n",
    "                queue.append(node.right)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def node_check(self, node:TreeNode, parent:TreeNode, ans:List[List[int]], queue:List[TreeNode])->List[List[int]]:\n",
    "        if not node:\n",
    "            return ans\n",
    "        res = []\n",
    "        while ans:\n",
    "            arr = ans.pop(0)\n",
    "            for i in range(len(arr)-1, -1, -1):\n",
    "                arr_copy = deepcopy(arr)\n",
    "                arr_copy.insert(i+1, node.val)\n",
    "                res.append(arr_copy)\n",
    "                if arr[i]==parent.val:\n",
    "                    break\n",
    "        queue.append(node)\n",
    "        return res\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        ans = [[root.val]]\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            ans = self.node_check(node.left, node, ans, queue)\n",
    "            ans = self.node_check(node.right, node, ans, queue)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "        elif root.left is None and root.right is None:\n",
    "            return [[root.val]]\n",
    "        elif root.left is None and root.right is not None:\n",
    "            r_ans = self.BSTSequences(root.right)\n",
    "            return [[root.val] + ans for ans in r_ans]\n",
    "        elif root.left is not None and root.right is None:\n",
    "            l_ans = self.BSTSequences(root.left)\n",
    "            return [[root.val] + ans for ans in l_ans]\n",
    "        else:\n",
    "            l_ans = self.BSTSequences(root.left)\n",
    "            r_ans = self.BSTSequences(root.right)\n",
    "\n",
    "            ans = []\n",
    "            for l in l_ans:\n",
    "                for r in r_ans:\n",
    "                    cans = self.stitch(l, r)\n",
    "                    for can in cans:\n",
    "                        ans.append([root.val] + can)\n",
    "            return ans\n",
    "\n",
    "    def stitch(self, l, r):\n",
    "        if len(l) == 0 and len(r) > 0:\n",
    "            return [r]\n",
    "        elif len(l) > 0 and len(r) == 0:\n",
    "            return [l]\n",
    "        else:\n",
    "            res = []\n",
    "            res_1 = self.stitch(l[1:], r)\n",
    "            for a1 in res_1:\n",
    "                res.append([l[0]] + a1)\n",
    "\n",
    "            res_2 = self.stitch(l, r[1:])\n",
    "            for a2 in res_2:\n",
    "                res.append([r[0]] + a2)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        else:\n",
    "            left = self.BSTSequences(root.left)\n",
    "            right = self.BSTSequences(root.right)\n",
    "            res = []\n",
    "            for i in left:\n",
    "                for j in right:\n",
    "                    res +=[[root.val]+z for z in self.mix(i,j)]\n",
    "            return res\n",
    "\n",
    "    def mix(self,L1,L2):\n",
    "        if not L1 or not L2:\n",
    "            return [L1 + L2]\n",
    "        else:\n",
    "            left = [[L1[0]]+z for z in self.mix(L1[1:],L2)]\n",
    "            right = [[L2[0]]+z for z in self.mix(L1,L2[1:])]\n",
    "            return left + right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        # if not left or not right:\n",
    "        #     tmp = left+right if left or right else [[]]\n",
    "        #     return list(map(lambda c:[root.val]+c,tmp))\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                func(l,r,[],res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "        ans = []\n",
    "        path = [root.val]\n",
    "        def dfs(q,cur):\n",
    "            if cur.left:q.append(cur.left)\n",
    "            if cur.right:q.append(cur.right)\n",
    "            if not q:# 边界，队列为空\n",
    "                ans.append(path.copy())\n",
    "            for i,nxt in enumerate(q):\n",
    "                path.append(nxt.val)\n",
    "                new_q = q[:i]+q[i+1:]\n",
    "                dfs(new_q,nxt)\n",
    "                path.pop()\n",
    "        dfs([],root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                func(l,r,[],res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        # if not left or not right:\n",
    "        #     tmp = left+right if left or right else [[]]\n",
    "        #     return list(map(lambda c:[root.val]+c,tmp))\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                func(l,r,[],res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        def merge(arr1, arr2):\n",
    "            if not arr1: return [arr2]\n",
    "            if not arr2: return [arr1]\n",
    "            res = []\n",
    "            nums = merge(arr1[1:], arr2)\n",
    "            for arr in nums:\n",
    "                res.append([arr1[0]]+arr)\n",
    "            nums = merge(arr1, arr2[1:])\n",
    "            for arr in nums:\n",
    "                res.append([arr2[0]]+arr)\n",
    "            return res\n",
    "\n",
    "        if not root: return [[]]\n",
    "        arr1 = self.BSTSequences(root.left)\n",
    "        arr2 = self.BSTSequences(root.right)\n",
    "        l1 = len(arr1[0])\n",
    "        l2 = len(arr2[0])\n",
    "        res = []\n",
    "        if l1 and l2:\n",
    "            for i in arr1:\n",
    "                for j in arr2:\n",
    "                    for arr in merge(i, j):\n",
    "                        res.append([root.val] + arr)\n",
    "        elif l1:\n",
    "            for i in arr1:\n",
    "                res.append([root.val] + i)\n",
    "        elif l2:\n",
    "            for i in arr2:\n",
    "                res.append([root.val] + i)\n",
    "        else:\n",
    "            res = [[root.val]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        if not left or not right:\n",
    "            tmp = left+right if left or right else [[]]\n",
    "            return list(map(lambda c:[root.val]+c,tmp))\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                func(l,r,[],res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        def weave(first, second, prefix):\n",
    "            if not first or not second:\n",
    "                return [prefix + first + second]\n",
    "\n",
    "            result = []\n",
    "            weave_first = weave(first[1:], second, prefix + [first[0]])\n",
    "            weave_second = weave(first, second[1:], prefix + [second[0]])\n",
    "\n",
    "            for w in weave_first:\n",
    "                result.append(w)\n",
    "\n",
    "            for w in weave_second:\n",
    "                result.append(w)\n",
    "\n",
    "            return result\n",
    "\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        result = []\n",
    "        prefix = [root.val]\n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                result.extend(weave(l, r, prefix))\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def dfs(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            dfs(l[1:],r,re+[l[0]],res)\n",
    "            dfs(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                dfs(l,r,[],res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        # if not left or not right:\n",
    "        #     tmp = left+right if left or right else [[]]\n",
    "        #     return list(map(lambda c:[root.val]+c,tmp))\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                func(l,r,[],res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "      if root == None:\n",
    "        return [[]]\n",
    "      \n",
    "      ans = []\n",
    "      l = deque()\n",
    "      u = []\n",
    "      if root.left != None:\n",
    "        u.append(root.left)\n",
    "      if root.right != None:\n",
    "        u.append(root.right)\n",
    "      l.append([[root.val],u])\n",
    "      \n",
    "      while l:\n",
    "        #print(l)\n",
    "        a,b = l.popleft()\n",
    "        if len(b) == 0:\n",
    "          ans.append(a)\n",
    "          continue\n",
    "        n = len(b)\n",
    "        for i in range(n):\n",
    "          u = b[:i]+b[i+1:]\n",
    "          if b[i].left != None:\n",
    "            u.append(b[i].left)\n",
    "          if b[i].right != None:\n",
    "            u.append(b[i].right)\n",
    "          l.append([a+[b[i].val],u])\n",
    "        \n",
    "      return ans\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "        left_seqs = self.BSTSequences(root.left) if root.left is not None else [[]]\n",
    "        right_seqs = self.BSTSequences(root.right) if root.right is not None else [[]]\n",
    "        seqs = []\n",
    "        for l in left_seqs:\n",
    "            for r in right_seqs:\n",
    "                seqs.extend(self.merge_sequences(l, 0, r, 0, [root.val]))\n",
    "        return seqs\n",
    "\n",
    "    def merge_sequences(\n",
    "        self,\n",
    "        left: List[int],\n",
    "        left_index: int,\n",
    "        right: List[int],\n",
    "        right_index: int,\n",
    "        temp_seq: List[int],\n",
    "    ) -> List[List[int]]:\n",
    "        if left_index == len(left) and right_index == len(right):\n",
    "            return [temp_seq]\n",
    "        if left_index == len(left):\n",
    "            return [temp_seq + right[right_index:]]\n",
    "        if right_index == len(right):\n",
    "            return [temp_seq + left[left_index:]]\n",
    "        return self.merge_sequences(\n",
    "            left, left_index + 1, right, right_index, temp_seq + [left[left_index]]\n",
    "        ) + self.merge_sequences(\n",
    "            left, left_index, right, right_index + 1, temp_seq + [right[right_index]]\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def printn(nodes, path):\n",
    "    l = []\n",
    "    for x in nodes:\n",
    "        l.append(x.val)\n",
    "    print(l, path)\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        ans = []\n",
    "        def dfs(nodes, path):\n",
    "            if not nodes:\n",
    "                ans.append(path[:])\n",
    "            for i, x in enumerate(nodes):\n",
    "                path.append(x.val)\n",
    "                next_nodes = nodes[:]\n",
    "\n",
    "                del next_nodes[i]\n",
    "                if x.left:\n",
    "                    next_nodes.append(x.left)\n",
    "                if x.right:\n",
    "                    next_nodes.append(x.right)\n",
    "                dfs(next_nodes, path)\n",
    "                # printn(next_nodes, path)\n",
    "                path.pop()\n",
    "        dfs([root],[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]] \n",
    "        \n",
    "        res = []\n",
    "        path = []\n",
    "        path.append(root.val)\n",
    "        def dfs(node, queue):\n",
    "            nonlocal path \n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "            if not queue:\n",
    "                res.append(path[:])\n",
    "                return \n",
    "            \n",
    "            for i in range(len(queue)):\n",
    "                node = queue[i]\n",
    "                path.append(node.val)\n",
    "                dfs(node, queue[:i] + queue[i+1:])\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(root, [])\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "\n",
    "        val_to_node={}\n",
    "        def dfs(node):\n",
    "            if node is not None:\n",
    "                val_to_node[node.val]=node\n",
    "            \n",
    "                if node.left is not None:\n",
    "                    dfs(node.left)\n",
    "\n",
    "                if node.right is not None:\n",
    "                    dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        # print(val_to_node)\n",
    "\n",
    "        result=[]\n",
    "        def backtracking(node, to_visit, visited, path):\n",
    "\n",
    "\n",
    "            visited.add(node.val)\n",
    "            to_visit.remove(node.val)\n",
    "            path.append(node.val)\n",
    "\n",
    "            for child in (node.left, node.right):\n",
    "                if child is not None and child not in visited:\n",
    "                    to_visit.add(child.val)\n",
    "\n",
    "            if len(to_visit)==0:\n",
    "                result.append(path.copy())\n",
    "                print(path)\n",
    "\n",
    "            for val_to_visit in to_visit.copy():\n",
    "                backtracking(val_to_node[val_to_visit],to_visit,visited,path)\n",
    "\n",
    "            for child in (node.left, node.right):\n",
    "                if child is not None and child not in visited:\n",
    "                    to_visit.remove(child.val)\n",
    "\n",
    "\n",
    "\n",
    "            to_visit.add(node.val)\n",
    "            visited.remove(node.val)\n",
    "            path.pop()\n",
    "\n",
    "\n",
    "\n",
    "        backtracking(root,set([root.val]),set(),[])\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        #广度加深度\n",
    "\n",
    "        self.outlist=[]\n",
    "\n",
    "        def BSTSe(allroot,this):\n",
    "            nowroot=allroot.copy()        \n",
    "            for i in allroot:\n",
    "                this.append(i.val)\n",
    "                now=i \n",
    "                nowroot.remove(i)\n",
    "                if now.left:\n",
    "                    nowroot.add(now.left)\n",
    "                if now.right:\n",
    "                    nowroot.add(now.right)\n",
    "                \n",
    "                if not nowroot:\n",
    "                    self.outlist.append(this[:])\n",
    "                else:\n",
    "                    BSTSe(nowroot,this)    \n",
    "\n",
    "                if now.left:\n",
    "                    nowroot.remove(now.left)\n",
    "                if now.right:\n",
    "                    nowroot.remove(now.right)\n",
    "                nowroot.add(now)\n",
    "                this.pop()\n",
    "\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        BSTSe(set([root]),[])\n",
    "        return self.outlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = list()\n",
    "        path = list()\n",
    "\n",
    "        def dfs(queue: List[TreeNode]) -> None:\n",
    "            if not queue:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "\n",
    "            for idx, node in enumerate(queue):\n",
    "                new_q = queue[:idx] + queue[idx+1:]\n",
    "                if node.left:\n",
    "                    new_q.append(node.left)\n",
    "                if node.right:\n",
    "                    new_q.append(node.right)\n",
    "                path.append(node.val)                \n",
    "                dfs(new_q)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs([root])\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        if not left or not right:\n",
    "            tmp = left+right if left or right else [[]]\n",
    "            return list(map(lambda c:[root.val]+c,tmp))\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                re = []\n",
    "                func(l,r,re,res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from itertools import product\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        res = list()\n",
    "        if root is None:\n",
    "            res.append(list())\n",
    "            return res\n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "\n",
    "        def merge(i: int, j: int, l: list[int], r: list[int], cur: list[int], m: int, n: int):\n",
    "            if i == m and j == n:\n",
    "                yield cur.copy()\n",
    "            if i < m:\n",
    "                cur.append(l[i])\n",
    "                yield from merge(i + 1, j, l, r, cur, m, n)\n",
    "                cur.pop()\n",
    "            if j < n:\n",
    "                cur.append(r[j])\n",
    "                yield from merge(i, j + 1, l, r, cur, m, n)\n",
    "                cur.pop()\n",
    "        \n",
    "        for l, r in product(left, right):\n",
    "            res.extend(merge(0, 0, l, r, [root.val], len(l), len(r)))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def n01(n_i, n0_i):\n",
    "    assert n0_i > 0\n",
    "    assert n_i > 0\n",
    "    all_list = []\n",
    "\n",
    "    def fill_next(cur_list, n, n0):\n",
    "        if n == 0:\n",
    "            all_list.append(cur_list)\n",
    "            return\n",
    "        if n0 == 0:\n",
    "            all_list.append(cur_list + [1 for _ in range(n)])\n",
    "            return\n",
    "        if n0 == n:\n",
    "            all_list.append(cur_list + [0 for _ in range(n)])\n",
    "            return\n",
    "        fill_next(cur_list + [0], n-1, n0-1)\n",
    "        fill_next(cur_list + [1], n-1, n0)\n",
    "\n",
    "    fill_next([], n_i, n0_i)\n",
    "    return all_list\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "\n",
    "        all_list_L = self.BSTSequences(root.left)\n",
    "        all_list_R = self.BSTSequences(root.right)\n",
    "\n",
    "        if (all_list_L == [[]]) and (all_list_R == [[]]):\n",
    "            return [[root.val]]\n",
    "        elif (all_list_L == [[]]):\n",
    "            return [[root.val] + tmp for tmp in all_list_R] \n",
    "        elif (all_list_R == [[]]):\n",
    "            return [[root.val] + tmp for tmp in all_list_L]\n",
    "        \n",
    "        all_list = []\n",
    "        n_L = len(all_list_L[0])\n",
    "        n_R = len(all_list_R[0])\n",
    "        for pattern in n01(n_L+n_R, n_L):\n",
    "            for iL in all_list_L:\n",
    "                for iR in all_list_R:\n",
    "                    cur_list = [root.val]\n",
    "                    p0 = 0\n",
    "                    p1 = 0\n",
    "                    for p in pattern:\n",
    "                        if p == 0:\n",
    "                            cur_list += [iL[p0]]\n",
    "                            p0 += 1\n",
    "                        else:\n",
    "                            cur_list += [iR[p1]]\n",
    "                            p1 += 1\n",
    "                    all_list.append(cur_list)\n",
    "        return all_list\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        if not left or not right:\n",
    "            tmp = left+right if left or right else [[]]\n",
    "            return list(map(lambda c:[root.val]+c,tmp))\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                re = []\n",
    "                func(l,r,re,res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        if not left or not right:\n",
    "            tmp = left+right if left or right else [[]]\n",
    "            return list(map(lambda c:[root.val]+c,tmp))\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                re = []\n",
    "                func(l,r,re,res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        results = []\n",
    "        ans = []\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "\n",
    "        # 回溯\n",
    "        def helper(queue):\n",
    "            if len(queue) == 0:\n",
    "                results.append(ans[::])\n",
    "            # 队列中有 n个元素\n",
    "            n = len(queue) # 当前有n个节点可选\n",
    "            for i in range(n):\n",
    "                # 这一步选择第i个节点\n",
    "                element = queue.popleft()\n",
    "                # 将element加入ans\n",
    "                ans.append(element.val)\n",
    "                if element.left:\n",
    "                    queue.append(element.left)\n",
    "                if element.right:\n",
    "                    queue.append(element.right)\n",
    "                # 回溯\n",
    "                helper(queue)\n",
    "                if element.right:\n",
    "                    queue.pop()\n",
    "                if element.left:\n",
    "                    queue.pop()\n",
    "                ans.pop()\n",
    "                queue.append(element)\n",
    "        helper(q)\n",
    "        return results\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def func(l,r,re,res):\n",
    "            # if tmp:\n",
    "            #     for i in range(len(re)):\n",
    "            #         re[i].append(tmp)\n",
    "            if not l or not r:\n",
    "                res.append(re+l+r)\n",
    "                return\n",
    "            func(l[1:],r,re+[l[0]],res)\n",
    "            func(l,r[1:],re+[r[0]],res)\n",
    "        \n",
    "        left = self.BSTSequences(root.left)\n",
    "        right = self.BSTSequences(root.right)\n",
    "        # print(left,right)\n",
    "        if not left or not right:\n",
    "            tmp = left+right if left or right else [[]]\n",
    "            return list(map(lambda c:[root.val]+c,tmp))\n",
    "        res = []\n",
    "        for l in left:\n",
    "            for r in right:\n",
    "                re = []\n",
    "                func(l,r,re,res)\n",
    "                print(res)\n",
    "                # res+=re\n",
    "        # print(res)\n",
    "        return list(map(lambda c:[root.val]+c,res))\n",
    "        \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:       \n",
    "\n",
    "\n",
    "\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def dfs(cur,q,path):\n",
    "\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            \n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return \n",
    "            \n",
    "            for k,v in enumerate(q):\n",
    "                newq = q[:k] +q[k+1:]\n",
    "                dfs(v,newq,path+[v.val])\n",
    "        dfs(root,[],[root.val])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        def sequences(partial, candidates):\n",
    "            if not candidates:\n",
    "                return [partial]\n",
    "\n",
    "            res = []\n",
    "            for node in list(candidates):\n",
    "                candidates.remove(node)\n",
    "                next_partial = partial + [node.val]\n",
    "                next_candidates = candidates.copy()\n",
    "                if node.left:\n",
    "                    next_candidates.add(node.left)\n",
    "                if node.right:\n",
    "                    next_candidates.add(node.right)\n",
    "\n",
    "                res += sequences(next_partial, next_candidates)\n",
    "                candidates.add(node)\n",
    "            return res\n",
    "\n",
    "        return sequences([], {root})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        result = []\n",
    "        if not root:return [[]]\n",
    "        def dfs(root, queue, path):\n",
    "            if root.left:\n",
    "                queue.append(root.left)\n",
    "            if root.right:\n",
    "                queue.append(root.right)\n",
    "            if not queue:\n",
    "                result.append(path)\n",
    "            for i, node in enumerate(queue):\n",
    "                extend_queue = queue[:i] + queue[i+1:]\n",
    "                dfs(node, extend_queue, path + [node.val])\n",
    "        dfs(root, [], [root.val])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# copied\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "\n",
    "        answer = []\n",
    "\n",
    "        def dfs(node: TreeNode, path: list, available: list):\n",
    "            if node.left:\n",
    "                available.append(node.left)\n",
    "            if node.right:\n",
    "                available.append(node.right)\n",
    "            if not available:\n",
    "                answer.append(path)\n",
    "\n",
    "            for i, next_node in enumerate(available):\n",
    "                dfs(next_node, path + [next_node.val], available[:i] + available[i + 1:])\n",
    "\n",
    "        dfs(root, [root.val], [])\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res=[]\n",
    "        def findPath(cur,q,path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i,nex in enumerate(q):\n",
    "                newq=q[:i]+q[i+1:]\n",
    "                findPath(nex,newq,path+[nex.val])\n",
    "        findPath(root,[],[root.val])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root==None:\n",
    "            return [[]]\n",
    "\n",
    "        l,d=recursion(root,[],{})\n",
    "        # print(l,d)\n",
    "        rel=recursion1([],[root.val],d,len(l))\n",
    "        return rel\n",
    "        \n",
    "def recursion(root,l,d):\n",
    "    l.append(root.val)\n",
    "    pl='null' if root.left==None else root.left.val\n",
    "    pr='null' if root.right==None else root.right.val\n",
    "    if root.val in d:\n",
    "        d[root.val].append([pl,pr])\n",
    "    else:\n",
    "        d[root.val]=[pl,pr]\n",
    "\n",
    "    if root.left!=None:\n",
    "        l,d=recursion(root.left,l,d)\n",
    "    if root.right!=None:\n",
    "        l,d=recursion(root.right,l,d)\n",
    "    return l,d\n",
    "def recursion1(rel,l,d,m):\n",
    "    if len(l)==m:\n",
    "        rel.append(l)\n",
    "        return rel\n",
    "    for il in l:\n",
    "        for j in d[il]:\n",
    "            # print(l,il,j)\n",
    "            if j not in l and (j !='null'):\n",
    "                rel=recursion1(rel,l+[j],d,m)\n",
    "    return rel\n",
    "\n",
    "    \n",
    "    \n",
    "        \n",
    "    \n",
    "      \n",
    "\n",
    "        \n",
    "    \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                ans.append(path)\n",
    "            for i, nex in enumerate(q):\n",
    "                newq = q[:i] + q[i+1:]\n",
    "                dfs(q[i], newq, path+[q[i].val])\n",
    "        dfs(root, path, [root.val])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def findPath(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                newq = q[:i] + q[i + 1:]\n",
    "                findPath(nex, newq, path + [nex.val])\n",
    "        findPath(root, [], [root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def findPath(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                newq = q[:i] + q[i + 1:]\n",
    "                findPath(nex, newq, path + [nex.val])\n",
    "        findPath(root, [], [root.val])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "\n",
    "        cd = {}\n",
    "        self.trav(root, cd)\n",
    "        n = len(cd.keys())\n",
    "        # print(cd)\n",
    "        \n",
    "        def backtracing(path: List, res: List, visited: List, candidates: List) -> None: \n",
    "            # print(path)\n",
    "            if len(path) == n:\n",
    "                res.append(list(path))\n",
    "                return \n",
    "            \n",
    "            for node in candidates:\n",
    "                if node in visited:\n",
    "                    continue \n",
    "                path.append(node.val)\n",
    "                visited.append(node)\n",
    "                tmp_candidates = candidates + cd[node]\n",
    "                backtracing(path, res, visited, tmp_candidates)\n",
    "                visited.pop()\n",
    "                path.pop()\n",
    "\n",
    "        res = []\n",
    "        visited = []\n",
    "        backtracing([root.val], res, visited, cd[root])\n",
    "        # print(res)    \n",
    "        return res \n",
    "\n",
    "    def trav(self, root: TreeNode, child_dict: Dict) -> None: \n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        child_dict[root] = []\n",
    "        if root.left:\n",
    "            child_dict[root].append(root.left)\n",
    "        if root.right:\n",
    "            child_dict[root].append(root.right)\n",
    "\n",
    "        self.trav(root.left, child_dict)    \n",
    "        self.trav(root.right, child_dict)\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def findPath(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                newq = q[:i] + q[i + 1:]\n",
    "                findPath(nex, newq, path + [nex.val])\n",
    "        findPath(root, [], [root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        self.ans = []\n",
    "        def recursion(curnodes, curans):\n",
    "            if not curnodes:\n",
    "                self.ans.append(curans)\n",
    "            n = len(curnodes)\n",
    "            for i in range(n):\n",
    "                node = curnodes[i]\n",
    "                if node.left and node.right:\n",
    "                    recursion(curnodes[:i] + curnodes[i+1:] + [node.left, node.right], curans+[node.val])\n",
    "                elif node.left:\n",
    "                    recursion(curnodes[:i] + curnodes[i+1:] + [node.left], curans+[node.val])\n",
    "                elif node.right:\n",
    "                    recursion(curnodes[:i] + curnodes[i+1:] + [node.right], curans+[node.val])\n",
    "                else:\n",
    "                    recursion(curnodes[:i] + curnodes[i+1:], curans+[node.val])\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        else:\n",
    "            recursion([root], [])\n",
    "            return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def findPuth(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                findPuth(q[i], q[0:i]+q[i+1:], path+[q[i].val])\n",
    "        findPuth(root, [], [root.val])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "        ans = []\n",
    "\n",
    "        def findpath(node, deque, path):\n",
    "            if node.left is not None:\n",
    "                deque.append(node.left)\n",
    "            if node.right is not None:\n",
    "                deque.append(node.right)\n",
    "            if len(deque) == 0:\n",
    "                ans.append(path)\n",
    "            for index in range(len(deque)):\n",
    "                new_deque = deque[:index] + deque[index+1:]\n",
    "                findpath(deque[index], new_deque, path + [deque[index].val])\n",
    "        findpath(root, [], [root.val])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res=[]\n",
    "        def findPath(cur,q,path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i,nex in enumerate(q):\n",
    "                newq=q[:i]+q[i+1:]\n",
    "                findPath(nex,newq,path+[nex.val])\n",
    "        findPath(root,[],[root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "\n",
    "        cd = {}\n",
    "        self.trav(root, cd)\n",
    "        n = len(cd.keys())\n",
    "        # print(cd)\n",
    "        \n",
    "        def backtracing(path: List, res: List, visited: List, candidates: List) -> None: \n",
    "            # print(path)\n",
    "            if len(path) == n:\n",
    "                res.append(list(path))\n",
    "                return \n",
    "            \n",
    "            for node in candidates:\n",
    "                if node in visited:\n",
    "                    continue \n",
    "                    \n",
    "                path.append(node.val)\n",
    "                visited.append(node)\n",
    "                tmp_candidates = candidates + cd[node]\n",
    "                backtracing(path, res, visited, tmp_candidates)\n",
    "                visited.pop()\n",
    "                path.pop()\n",
    "\n",
    "        res = []\n",
    "        visited = []\n",
    "        backtracing([root.val], res, visited, cd[root])\n",
    "        # print(res)    \n",
    "        return res \n",
    "\n",
    "    def trav(self, root: TreeNode, child_dict: Dict) -> None: \n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        child_dict[root] = []\n",
    "        if root.left:\n",
    "            child_dict[root].append(root.left)\n",
    "        if root.right:\n",
    "            child_dict[root].append(root.right)\n",
    "\n",
    "        self.trav(root.left, child_dict)    \n",
    "        self.trav(root.right, child_dict)\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return [[]]\n",
    "        ans_all=[]\n",
    "        def dfs(root, que, path):\n",
    "            if root.left: \n",
    "                que.append(root.left)\n",
    "            if root.right: \n",
    "                que.append(root.right)\n",
    "            if not que: ans_all.append(path)\n",
    "            for i in range(len(que)):\n",
    "                dfs(que[i], que[0:i]+que[i+1:], path+[que[i].val])\n",
    "        dfs(root, [], [root.val])\n",
    "        return ans_all\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "\n",
    "        cd = {}\n",
    "        self.trav(root, cd)\n",
    "        n = len(cd.keys())\n",
    "        # print(cd)\n",
    "        \n",
    "        def backtracing(path: List, res: List, visited: List, candidates: List) -> None: \n",
    "            # print(path)\n",
    "            if len(path) == n:\n",
    "                res.append(list(path))\n",
    "                return \n",
    "            \n",
    "            for node in candidates:\n",
    "                if node in visited:\n",
    "                    continue \n",
    "                    \n",
    "                path.append(node.val)\n",
    "                visited.append(node)\n",
    "                tmp_candidates = candidates + cd[node]\n",
    "                backtracing(path, res, visited, tmp_candidates)\n",
    "                visited.pop()\n",
    "                path.pop()\n",
    "\n",
    "        res = []\n",
    "        visited = []\n",
    "        backtracing([root.val], res, visited, cd[root])\n",
    "        # print(res)    \n",
    "        return res \n",
    "\n",
    "    def trav(self, root: TreeNode, child_dict: Dict) -> None: \n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        child_dict[root] = []\n",
    "        if root.left:\n",
    "            child_dict[root].append(root.left)\n",
    "        if root.right:\n",
    "            child_dict[root].append(root.right)\n",
    "\n",
    "        self.trav(root.left, child_dict)    \n",
    "        self.trav(root.right, child_dict)\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "\n",
    "        def dfs(root, que, path):\n",
    "            if root.left: que.append(root.left)\n",
    "            if root.right: que.append(root.right)\n",
    "            if not que:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(que):\n",
    "                newq = que[:i] + que[i+1:]\n",
    "                dfs(nex, newq, path+[nex.val])\n",
    "        res = []\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        dfs(root, [], [root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        # 每一个节点都必须排在它的子孙结点前面\n",
    "        def backtrack(curr, queue, path): # queue储存这一轮可以插入的所有节点\n",
    "            if curr.left: # 这一轮访问了curr，把它的左右子树加到下一轮候选\n",
    "                queue.append(curr.left)\n",
    "            if curr.right:\n",
    "                queue.append(curr.right)\n",
    "            if not queue: # 如果空了，说明全遍历完了\n",
    "                res.append(path)\n",
    "                return \n",
    "            for i, nxt in enumerate(queue):\n",
    "                next_queue = queue[:i] + queue[i + 1:]  # 相当于取出queue[i]这个元素，把它排在数组里，然后下一轮看queue[i]有没有左右子树，并且和剩下的next_queue里的元素一起继续遍历\n",
    "                backtrack(nxt, next_queue, path + [nxt.val])\n",
    "\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        backtrack(root, [], [root.val])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def BFS(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                newq = q[:i] + q[i + 1:]\n",
    "                BFS(nex, newq, path + [nex.val])\n",
    "        BFS(root, [], [root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def findPath(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                newq = q[:i] + q[i + 1:]\n",
    "                findPath(nex, newq, path + [nex.val])\n",
    "        findPath(root, [], [root.val])\n",
    "        return res\n",
    "\n",
    "# 使用一个queue存储下个所有可能的节点\n",
    "# 然后选择其中一个作为path的下一个元素\n",
    "# 递归直到queue元素为空\n",
    "# 将对应的path加入结果中\n",
    "# 由于二叉搜索树没有重复元素, 而且每次递归的使用元素的顺序都不一样, 所以自动做到了去重\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "    \n",
    "        if not root:\n",
    "            return [[]]\n",
    "        \n",
    "        result=[]\n",
    "\n",
    "        def back_track(root,queue,cur):\n",
    "\n",
    "            if root.left:\n",
    "                queue.append(root.left)\n",
    "            if root.right:\n",
    "                queue.append(root.right)           \n",
    "\n",
    "            if not queue:\n",
    "                result.append(cur)\n",
    "                return\n",
    "\n",
    "            for index,tree in enumerate(queue):\n",
    "                new_queue=queue[:index]+queue[index+1:]\n",
    "                back_track(tree,new_queue,cur+[tree.val])\n",
    "\n",
    "        back_track(root,[],[root.val])\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def findPath(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                newq = q[:i] + q[i + 1:]\n",
    "                findPath(nex, newq, path + [nex.val])\n",
    "        findPath(root, [], [root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def findPath(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                newq = q[:i] + q[i + 1:]\n",
    "                findPath(nex, newq, path + [nex.val])\n",
    "        findPath(root, [], [root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        res = []\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "        temp = [root.val]\n",
    "        def help(root, queue, path):\n",
    "            if root.left:\n",
    "                queue.append(root.left)\n",
    "            if root.right:\n",
    "                queue.append(root.right)\n",
    "            if len(queue)==0:\n",
    "                res.append(temp+path)\n",
    "            for i, next_root in enumerate(queue):\n",
    "                next_queue = queue[:i] + queue[i+1:]\n",
    "                help(next_root, next_queue, path+[next_root.val])\n",
    "        help(root, [], [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return [[]]\n",
    "\n",
    "        cd = {}\n",
    "        self.trav(root, cd)\n",
    "        n = len(cd.keys())\n",
    "        # print(cd)\n",
    "        \n",
    "        def backtracing(path: List, res: List, visited: List, candidates: List) -> None: \n",
    "            # print(path)\n",
    "            if len(path) == n:\n",
    "                res.append(list(path))\n",
    "                return \n",
    "            \n",
    "            for node in candidates:\n",
    "                if node in visited:\n",
    "                    continue \n",
    "                    \n",
    "                path.append(node.val)\n",
    "                visited.append(node)\n",
    "                tmp_candidates = candidates + cd[node]\n",
    "                backtracing(path, res, visited, tmp_candidates)\n",
    "                visited.pop()\n",
    "                path.pop()\n",
    "\n",
    "        res = []\n",
    "        visited = []\n",
    "        backtracing([root.val], res, visited, cd[root])\n",
    "        # print(res)    \n",
    "        return res \n",
    "\n",
    "    def trav(self, root: TreeNode, child_dict: Dict) -> None: \n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        child_dict[root] = []\n",
    "        if root.left:\n",
    "            child_dict[root].append(root.left)\n",
    "        if root.right:\n",
    "            child_dict[root].append(root.right)\n",
    "\n",
    "        self.trav(root.left, child_dict)    \n",
    "        self.trav(root.right, child_dict)\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences_wrong(self, root: TreeNode) -> List[List[int]]:\n",
    "        st=TreeNode(root[0])\n",
    "        def insertnode(st,curval):\n",
    "            if st==None:\n",
    "                return TreeNode(curval)\n",
    "            if curval>st.val:\n",
    "                st.right=insertnode(st.right,curval)\n",
    "            elif curval<st.val:\n",
    "                st.left=insertnode(st.left,curval)\n",
    "            return st\n",
    "\n",
    "        for i in range(1,len(root)):\n",
    "            insertnode(st,root[i])\n",
    "\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        ans_all=[]\n",
    "\n",
    "        def dfs(root,que,path):\n",
    "            if root.left:\n",
    "                que.append(root.left)\n",
    "            if root.right:\n",
    "                que.append(root.right)\n",
    "            if not que:\n",
    "                ans_all.append(path)\n",
    "            for i in range(len(que)):\n",
    "                dfs(que[i],que[0:i]+que[i+1:],path+[que[i].val])\n",
    "        \n",
    "        dfs(root,[],[root.val])\n",
    "        return ans_all\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        def findpath(queue, cur, path):\n",
    "            if cur.left:\n",
    "                queue.append(cur.left)\n",
    "            if cur.right:\n",
    "                queue.append(cur.right)\n",
    "            \n",
    "            if not queue:\n",
    "                res.append(path)\n",
    "                return\n",
    "            \n",
    "            for i, node in enumerate(queue):\n",
    "                next_queue = queue[:i] + queue[i+1:]\n",
    "                findpath(next_queue, node, path+[node.val])\n",
    "        \n",
    "        res = []\n",
    "        findpath([], root, [root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        res = []\n",
    "        def findPath(cur, q, path):\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            if not q:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i, nex in enumerate(q):\n",
    "                #newq = q[:i] + q[i + 1:]\n",
    "                newq = q[:i] + q[i+1:]\n",
    "                #findPath(nex, newq, path + [nex.val])\n",
    "                findPath(nex, newq, path + [nex.val])\n",
    "        findPath(root, [], [root.val])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def BSTSequences(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return [[]]\n",
    "        ret = []\n",
    "\n",
    "        def dfs(n, l, p):\n",
    "            if n == 0:\n",
    "                ret.append(p)\n",
    "\n",
    "            for i in range(n):\n",
    "                _p = p[:]\n",
    "                _p.append(l[i].val)\n",
    "                \n",
    "                _n = n - 1\n",
    "                _l = l[:i] + l[i + 1:]\n",
    "\n",
    "                if l[i].left:\n",
    "                    _l.append(l[i].left)\n",
    "                    _n += 1\n",
    "\n",
    "                if l[i].right:\n",
    "                    _l.append(l[i].right)\n",
    "                    _n += 1\n",
    "\n",
    "                dfs(_n, _l, _p)\n",
    "        \n",
    "        dfs(1, [root], [])\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
